package com.midea.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 全排列，并将结果放在数组里
 * DFS算法*/
public class Solution {
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        //permute(nums);

        System.out.println(permute(nums));
    }

    public static List<List<Integer>> permute(int[] nums) {
        return dfs(nums,new boolean[nums.length],new ArrayList<>(),new ArrayList<>());
    }
    public static List<List<Integer>> dfs(int[] nums,boolean[] status,List<Integer> res,List<List<Integer>> result) {
        if (nums.length == res.size()){
            List<Integer> temp = new ArrayList<>();
            temp.addAll(res);
            result.add(temp);
            return result;
        }
        for (int i = 0; i < nums.length;i++){
            int c = nums[i];
            if (!status[i]){
                res.add(c);
                status[i] = true;
                dfs(nums,status,res,result);
                res.remove(res.size()-1);
                status[i] = false;
            }
        }
        return result;
    }
}
